package sort;

public class SelectionSort {
    /**
     * 选择排序：
     * 创建两层循环，外层循环i表示排序进度
     * tmp保存当前i下标，内层循环j表示从i的下一个下标开始依次对比，当j下标值比tmp下标值小时，tmp更新
     * 当走完while循环，此时tmp即是从i起往后最小元素的下标
     * 直接将i下标与tmp下标元素交换即可
     * */

    /**
     * 该方法书写过程不简洁，故更改*/
    public static void selectionSort(int[] array) {
        int len = array.length;
        for(int i = 0; i < len; i++) {
            int j = i+1;
            int tmp = i;
            while(j<len) {
                if(array[tmp]>array[j]) {
                    tmp = j;
                }
                j++;
            }
            int swap = array[i];
            array[i] = array[tmp];
            array[tmp] = swap;
        }
    }

    /**
     * 选择排序-plus版本
     * 此种代码书写方式优点：
     * 1，更加简洁，代码逻辑一目了然
     * 2，循环效率高
     * 3，封装性好，代码课重复利用程度高*/
    public static void selectSort(int[] array) {
        for(int i = 0; i < array.length; i++) {
            int minIndex = i;
            for(int j = i+1; j < array.length; j++) {
                if(array[minIndex] > array[j]) {
                    minIndex = j;
                }
            }
            swap(array,i,minIndex);
        }
    }

    private static void swap(int[] array, int i, int j) {
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }

    /**
     * 双向选择排序
     * 遍历一遍，同时记录当前最大值和最小值的下标*/
    public static void doubleSelectSort(int[] array) {
        int left = 0;
        int right = array.length-1;
        while(left<right) {
            int minIndex = left;
            int maxIndex = left;
            for(int i = left+1; i <= right; i++) {
                if(array[i] < array[minIndex]) {
                    minIndex = i;
                }
                if(array[i] > array[maxIndex]) {
                    maxIndex = i;
                }
            }
            swap(array,left,minIndex);
            //为了防止maxIndex的位置在left位置，故需要判断
            if(maxIndex == left) {
                maxIndex = minIndex;
            }
            swap(array,right,maxIndex);

            left++;
            right--;
        }
    }

    /**
     * 堆排序
     * 将传过来的数组修改为大根堆 再使用堆排序*/

    /**
     * 向下调整-siftDown
     * 从最后一棵子树开始将其调整为大根堆
     */

    /**
     * 复习siftDown时遇见的问题：
     *  由于我错误地理解了向下调整这一方法，从而导致我困在这里一个小时
     *  向下调整是对单个子树调整地手段*/
    private static void siftDown(int[] array,int len, int parent) {
        int child = parent*2+1;
        while(child < len) {
            if((child+1)<len && array[child+1]>array[child]) {
                child = child+1;
            }
            if(array[parent] < array[child]) {
                swap(array,child,parent);
                parent = child;
                child = parent*2+1;
            } else {
                break;
            }
        }
    }


    /**
     * 建堆*/
    public static void createHeap(int[] array) {
        int parent = (array.length-1-1)/2;
        while(parent>=0) {
            siftDown(array,array.length,parent);
            parent--;
        }
    }

    /**
     * 堆排序
     * 原理：
     * 在大根堆地基础上，创建局部变量end记录最后一个节点地下标
     * 将0小标 和 end下标 值交换，再使用向下调整维护 [0,end)范围的元素，end--
     * 当end==0时，0无需和0交换，故循环结束，当堆按照下标排列时 ，值为升序*/
    public static void heapSort(int[] array) {
        int end = array.length-1;
        while(end>0) {
            swap(array,0,end);
            siftDown(array,end,0);
            end--;
        }
    }

    /**
     * 冒泡排序*/
    public static void bubbleSort(int[] array) {
        for(int i = 0; i < array.length-1; i++) {
            boolean flag = false;
            for(int j = 0; j < array.length-1-i; j++) {
                if(array[j]>array[j+1]) {
                    swap(array,j,j+1);
                    flag = true;
                }
            }
            //若是在一轮循环中均没有进入if语句，则代表已经有序
            if(!flag) {
                break;
            }
        }
    }

    /**
     * 快速排序
     * 类似于二叉树，通过不断按照特定值分割链表以确定其位置*/
    public static void quickSort(int[] array) {
        //为了保证接口的统一性，此方法为套壳
        quick(array,0,array.length-1);
    }
    private static void quick(int[] array, int start, int end) {
        if(start>=end) {
            return;
        }
        //找到基准值
        int pivot = partitionHole(array,start,end);
        //递归调整左右
        quick(array,start,pivot-1);
        quick(array,pivot+1,end);
    }
    /**
     * 出现的情况：
     * 当我先将left遍历放在前面的时候，排序结果出现错误
     *  --上述问题的原因：由于我是固定将left设为基准值。当最后一次相遇时，我需要将相遇值与基准值交换
     *    若是当先遍历left时，其相遇值必定为大于基准值的数，此时将大于基准值的数与left交换
     *    会导致左右子树不是按照基准值分割放置*/
    /**
     * Hoare法*/
    private static int partitionHoare(int[] array, int left, int right) {
        //每次都以left为基准值
        int tmp = array[left];
        int record = left;

        while(left<right) {
            //为了避免数组越界，判断条件之前需要添加left<right（避免出现没有左/右子树的情况）
            while(left<right && array[right]>=tmp) {
                right--;
            }
            while(left<right && array[left]<=tmp) {
                left++;
            }
            swap(array,left,right);
        }
        //出循环则表示left 与 right相遇，只需将基准值与该值交换 并返回当前基准值下标即可
        swap(array,record,left);
        return left;
    }

    /**
     * 挖坑法*/
    private static int partitionHole(int[] array, int left, int right) {
        int tmp = array[left];
        while(left<right) {
            while(left<right && array[right]>=tmp) {
                right--;
            }
            //在挖坑法中，这两个swap函数其实无需调用，直接赋值即可
            swap(array,left,right);
            while(left<right && array[left]<=tmp) {
                left++;
            }
            swap(array,left,right);
        }
        array[left] = tmp;
        return left;
    }

    /**
     * 双指针法
     * prev用于维护小于基准值的数据*/
}

